package Bit;
import java.util.*;
  class SevenSort {
      //冒泡排序优化版
      public static void bubbleSort(int []arr)
      {
          for(int i=0;i<arr.length-1;i++) {
              boolean isSwaped = false;
              for(int j=0;j<arr.length-1-i;j++)
              {
                  if(arr[j]>arr[j+1])
                  {
                      swap(arr,j,j+1);
                      isSwaped=true;
                  }
              }
          }
      }
      //二分法优化直接插入排序
      public  static void insertionSortBS(int[]arr)
      {
          for (int i = 1; i < arr.length; i++) {
              int val = arr[i];
              int left = 0;
              int right = i;
              while (left < right) {
//                int mid = left + ((right - left) >> 1);
                  int mid = (left + right) >> 1;
                  if (val < arr[mid]) {
                      right = mid;
                  }else {
                      // val >= arr[mid]
                      left = mid + 1;
                  }
              }
              // 搬移left..i的元素
              for (int j = i; j > left; j--) {
                  arr[j] = arr[j - 1];
              }
              // left就是val插入的位置
              arr[left] = val;
          }
      }

      //直接插入排序
      public static void insertionSort(int []arr)
      {
          //已排序区间[0,i]
          //未排序区间[i...n]
          for(int i=1;i<arr.length;i++)
          {
              for(int j=i;j>0&&arr[j]<arr[j-1];j--)
              {
                  swap(arr,j,j-1);
              }
          }
      }
      //双向选择排序
      public static void selectionSortOP(int []arr)
      {
          int low=0;
          int high=arr.length-1;
          while(low<=high)
          {
              int min=low;//找到无序区间的最小值
              int max=low;//找到无序区间的最大值
              for(int i=low+1;i<=high;i++)
              {
                  if(arr[i]<arr[min])
                  {
                      min=i;
                  }
                  if(arr[i]>arr[max])
                  {
                      max=i;
                  }
              }
              swap(arr,low,min);
              if(max==low)
              {
                  max=min;
              }
              swap(arr,max,high);
              low+=1;
              high-=1;
          }
      }
      //选择排序
    public static void selectionSort(int []arr)
    {
        //无序区间[0，i]，有序区间[]
  for(int i=0;i<arr.length-1;i++)
  {
      int min=i;
      for(int j=i+1;j< arr.length;j++)
      {
          if(arr[j]<arr[min])
          {
              min=j;
          }
      }
      swap(arr,min,i);
  }


    }
    public  static void swap(int []arr,int left,int right)
    {
        int temp=0;
        temp=arr[right];
        arr[right]=arr[left];
        arr[left]=temp;
    }

}